/**
 * File: Scatter.h
 *
 * Integrantes:
 * @author Jormar Arellano		(05-37840)	<jormar.arellano@gmail.com>
 * @author Sabrina Fernández	(05-38163)	<sabrinamfm@gmail.com>
 */

#ifndef SCATTER_H
#define	SCATTER_H

#include "graph.h"

#ifdef	__cplusplus
extern "C" {
#endif

/* * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Parametros del algoritmo
 * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/** 
 * Tamano de la poblacion inicial
 */
int scatter_population_size;

/** 
 * Limite de la coloracion en los procedimientos de diversificacion
 */
int scatter_initial_k;

/** 
 * Numero de mejores individuos que se tomaran de la poblacion inicial
 */
int scatter_b;

/** 
 * Numero de individuos diversos que se tomaran de la poblacion inicial
 */
int scatter_d;

/** 
 * Imprime informacion verbose.
 * */
int scatter_verbose;

/**
 * Inicializa las constantes con valores por defecto.
 */
void scatter_defaults();

typedef struct {
    // Particion de vertices; ArrayList(ArrayList(Vertex))
    ArrayList *partition;

    // Indica si no se ha usado en la generacion de subconj.
    int isNew;

    // Numero de conflictos que esta configuracion genera
    int numConflicts;
} Configuration;

/**
 * Crea una nueva configuracion vacia
 */
Configuration *newConfiguration();

/**
 * Elimina una configuracion
 */
void freeConfiguration(Configuration *c);

/**
 * Dos configuraciones son iguales si todos sus vertices
 * deben ser pintados del mismo color
 */
int compareConfigurationByVertexId(ArrayListValue v1, ArrayListValue v2);

/**
 * Determina cual de las configuraciones es mejor
 * Basado en una funcion de calidad
 */
int compareConfigurationByBest(ArrayListValue v1, ArrayListValue v2);

/**
 * Compara dos configuraciones en base a su diversidad
 */
int compareConfigurationByDiverse(ArrayListValue v1, ArrayListValue v2);

/**
 * Dada una particion de vertices, pinta el grafo
 * con los colores adecuados
 */
void paintGraphfromPartition(Graph *graph, ArrayList *Pi);

/**
 * Pinta un grafo segun la particion, pero lo hace sin
 * verificar conflictos, ni nada mas
 */
void dummyPaintGraphFromPartition(Graph *graph, ArrayList *Pi);

/**
 * Reserva memoria nueva para una particion
 */
ArrayList *copyPartition(ArrayList *P);

/**
 * Elimina la memoria usada por una particion
 */
void freePartition(ArrayList *P);

/**
 * Calcula el numero de conflictos que tiene una coloracion
 * con la configuracion dada
 */
int calculePartitionConflicts(Graph *graph, ArrayList *P);

/**
 * Metodo de diversificacion.
 * @return  Una particion de los vertices.
 */
ArrayList *diversification_method(const Graph * graph);

/**
 * Fase de mejora para el algoritmo.
 * Podria ser o LocarlSearch, o tabuSearch
 */
Graph *(*scatter_imp_method)(Graph *graph);

/**
 * Genera todos los sunconjuntos del conjunto de referencia
 * @return  ArrayList(ArrayList(Configuration *)), es decir,
 *          una lista con los conjuntos de configuraciones.
 */
ArrayList *scatter_subsetGeneration(ArrayList *P);

/**
 * Elimina la memoria usada por la estructura creada en
 * scatter_subsetGeneration()
 */
void scatter_freeSubets(ArrayList *subset);

/**
 * Combina dos soluciones en una sola
 */
Configuration *scatter_confCombination(ArrayList *p);

/**
 * Funcion que evalua que tan buena es una configurarion.
 * Esta funcion en particular, cuenta el numero de conflictos
 * que tiene una coloracion bajo esta configuracion.
 */
long scatter_evaluation(Configuration *c);

/**
 * Aplica Scatter.
 */
Graph *scatter(Graph *graph);

#ifdef	__cplusplus
}
#endif

#endif

